// =============================================================================
//
// BloomFilter.h
// -- Counting Bloom filter
//
// =============================================================================

#ifndef __BLOOMFILTER_H__
#define __BLOOMFILTER_H__

#include "util/Pool.h"
#include "util/Vector.h"

// =============================================================================
// class BloomFilter
// =============================================================================

template< class K >
class BloomFilter {

  public:

    // Overloaded to force use of CALLOC/FREE
    NEW_DELETE_OPERATORS_INLINE_H(BloomFilter,NoSuper);

    BloomFilter( unsigned size,
                 Vector< unsigned (*)(K) > hashFunctions );
    ~BloomFilter( );

    BloomFilter< K >& clear( void );
    bool contains( K key );
    unsigned count( );
    BloomFilter< K >& insert( K key );
    BloomFilter< K >& remove( K key );
    BloomFilter< K >& visit( K key, void (*visitor)(unsigned) );    
    BloomFilter< K >& insertAll( BloomFilter< K > const& rhs );

    // For stats
    BloomFilter< K >& recordFalsePositive( void ) { numFalsePositive++;
                                                   return (*this); }
    unsigned getNumLookup( void )        { return numLookup; }
    unsigned getNumHit( void )           { return numHit; }
    unsigned getNumMiss( void )          { return numMiss; }
    unsigned getNumFalsePositive( void ) { return numFalsePositive; }
    unsigned getNumInsert( void )        { return numInsert; }
    unsigned getNumRemove( void )        { return numRemove; }

  private:

    unsigned* values;
    unsigned size;
    Vector< unsigned (*)(K) > hashFunctions;

    // Stats
    unsigned numLookup;          // number of calls to contains()
    unsigned numHit;             // how many times contains() returned true
    unsigned numMiss;            // how many times contains() returned false
    unsigned numFalsePositive;   // how many times contains() erroneously returned true
    unsigned numInsert;          // number of calls to insert()
    unsigned numRemove;          // number of calls to remove()
};



// =============================================================================
// BloomFilter
// =============================================================================
template< class K >
BloomFilter< K >::BloomFilter( unsigned _size,
                               Vector< unsigned (*)(K) > _hashFunctions )
{
    values = (unsigned*)CALLOC(_size, sizeof(unsigned));
    size = _size;
    hashFunctions = _hashFunctions;

    for (unsigned i = 0; i < size; i++) {
        values[i] = 0;
    }

    numLookup = 0;
    numHit = 0;
    numMiss = 0;
    numFalsePositive = 0;
    numInsert = 0;
    numRemove = 0;
}



// =============================================================================
// ~BloomFilter
// =============================================================================
template< class K >
BloomFilter< K >::~BloomFilter( void )
{
    FREE(values);
}



// =============================================================================
// clear
// -- Make Bloom filter empty
// =============================================================================
template< class K >
BloomFilter< K >&
BloomFilter< K >::clear( void )
{
    for (unsigned i = 0; i < size; i++) {
        values[i] = 0;
    }

    return (*this);
}



// =============================================================================
// contains
// -- Is it contained in the BloomFilter?
// =============================================================================
template< class K >
bool BloomFilter< K >::contains( K key )
{
    numLookup++;

    for (unsigned i = 0; i < hashFunctions.size(); i++) {
        unsigned hash = hashFunctions[i](key) % size;
        if (values[hash] < 1) {
            numMiss++;
            return false;
        }
    }

    numHit++;

    return true;
}



// =============================================================================
// count
// -- How many are set?
// =============================================================================
template< class K >
unsigned BloomFilter< K >::count( )
{
    unsigned count = 0;

    for (unsigned i = 0; i < size; i++) {
        if (values[i] > 0) {
            count++;
        }
    }

    return count;
}



// =============================================================================
// insert
// -- Insert in BloomFilter
// =============================================================================
template< class K >
BloomFilter< K >&
BloomFilter< K >::insert( K key )
{
    numInsert++;

    for (unsigned i = 0; i < hashFunctions.size(); i++) {
        unsigned hash = hashFunctions[i](key) % size;
        values[hash]++;
    }

    return (*this);
}



// =============================================================================
// remove
// -- Remove from BloomFilter
// =============================================================================
template< class K >
BloomFilter< K >&
BloomFilter< K >::remove( K key )
{
    numRemove++;

    for (unsigned i = 0; i < hashFunctions.size(); i++) {
        unsigned hash = hashFunctions[i](key) % size;
        values[hash]--;
    }

    return (*this);
}



// =============================================================================
// visit
// -- Apply visitor function to value associated with key
// =============================================================================
template< class K >
BloomFilter< K >&
BloomFilter< K >::visit( K key, void (*visitor)(unsigned) )
{
    for (unsigned i = 0; i < hashFunctions.size(); i++) {
        unsigned hash = hashFunctions[i](key) % size;
        visitor(values[hash]);
    }

    return (*this);
}



// =============================================================================
// insertAll
// -- Makes this Bloom filter the union of the previous contents
// and the contents of rhs.  Only works if the sizes and hash
// functions are identical. 
// =============================================================================
template< class K >
BloomFilter< K >&
BloomFilter< K >::insertAll( BloomFilter< K > const& rhs )
{
    ASSERT(hashFunctions == rhs.hashFunctions);
    ASSERT(size == rhs.size);

    for (unsigned i = 0; i < size; i++) {
        values[i] += rhs.values[i];
    }

    return (*this);
}



#endif // __BLOOMFILTER_H__



// =============================================================================
//
// End of BloomFilter.h
//
// =============================================================================
